1901A - Line Trip - CodeForces Solution


math

Please click on ads to support us..

C++ Code:

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef unsigned long long ull;
#define mod 1000000007
#define pb push_back
#define int ll
#define sortv(arr) sort(arr.begin(), arr.end())
#define sorta(arr, n) sort(arr, arr + n)
#define get_inout_fast            \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define no cout << "NO" << endl;
#define yes cout << "YES" << endl;
#define print(x) cout << x << endl;
#define vi vector<int>
#define vpi vector<pair<int, int>>
#define vvi vector<vector<int>>
#define vvs vector<vector<string>>
#define vvc vector<vector<char>>
#define loop(n) for (int i = 0; i < n; i++)
#define loop1(n) for (int j = 0; j < n; j++)
#define all(v) v.begin(), v.end()

int n;
bool poss(vector<int> &nums, int x, int dt)
{
    int curr = 0;
    for (int i = 0; i < n; i++)
    {
        int dis = nums[i] - curr;
        if (dis > x)
            return false;
        curr = nums[i];
    }
    int dis = 2*(dt - nums[n - 1]);
    if (dis > x)
        return false;
    return true;
}

void accio()
{
   
    int x;
    cin >> n >> x;
    vi a(n);
    loop(n) cin >> a[i];
    int low = 0, high = 1e9, ans = INT_MAX;
    while (low <= high)
    {
        int md = (low + high)/2;
        if (poss(a, md, x))
        {
            ans = md;
            high = md - 1;
        }
        else
        {
            low = md + 1;
        }
    }
    cout << ans << endl;
}
signed main()
{
    get_inout_fast
#ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t = 1;
    cin >> t;
    while (t--)
        accio();
    return 0;
}


Comments

Submit
0 Comments
More Questions

1041C - Coffee Break
507A - Amr and Music
1041D - Glider
1486A - Shifting Stacks
1389B - Array Walk
71B - Progress Bar
701A - Cards
545A - Toy Cars
1538E - Funny Substrings
234A - Lefthanders and Righthanders
1611D - Weights Assignment For Tree Edges
197A - Plate Game
1474A - Puzzle From the Future
6B - President's Office
1405B - Array Cancellation
431C - k-Tree
101A - Homework
1642C - Great Sequence
1523B - Lord of the Values
1406C - Link Cut Centroids
2409. Count Days Spent Together
2410. Maximum Matching of Players With Trainers
1604C - Di-visible Confusion
997A - Convert to Ones
218A - Mountain Scenery
486B - OR in Matrix
1405A - Permutation Forgery
1733A - Consecutive Sum
1733B - Rule of League
1733C - Parity Shuffle Sorting